Competición de factorización RSA

La Competición de factorización RSA fue un desafío propuesto por los Laboratorios RSA el 18 de marzo de 1991 para fomentar la investigación en la teoría computacional de números y la dificultad práctica de la factorización de números enteros grandes. Publicaron una lista de semiprimos (números que tienen exactamente dos factores primos) conocida como los números RSA, con un premio en metálico para la factorización con éxito de algunos de ellos. El más pequeño de todos, un número con 100 cifras decimales conocido como RSA-100 fue factorizado en pocos días^{[cita requerida]}, pero la mayoría de los números más grandes aún no han sido factorizados y se espera que permanezcan así durante bastante tiempo. La compañía RSA canceló la competición en el año 2007.

Este desafío estaba diseñado para seguir el ritmo al estado del arte en la factorización de enteros. Una aplicación importante es la elección de la longitud de la clave del algoritmo de cifrado mediante clave pública de RSA. Los avances en este desafío deberían ser un indicador de qué longitudes de clave son todavía seguras y por cuánto tiempo. Como los laboratorios RSA son los proveedores de los productos basados en RSA, el desafío se usa como incentivo a la comunidad académica para atacar el núcleo de sus soluciones, esto es, para comprobar su fortaleza.

Los primeros números RSA generados desde RSA-100 hasta RSA-500 fueron etiquetados de acuerdo con su número de cifras decimales; sin embargo, a partir de RSA-576 se cuentan las cifras en el sistema binario. La excepción a esto es el RSA-617, que fue creado antes del cambio del sistema de numeración.

Matemáticas

Sea $n$ un número RSA producto de dos primos $p$ y $q$ , de forma que

n=pq

.

El problema es encontrar esos dos primos, conociendo solo $n$ .

Sea $s=p+q$ ; entonces los valores de algunas funciones aritméticas básicas son

d(n)=2

,

\phi (n)=(p-1)(q-1)=n+1-s

,

\sigma (n)=(p+1)(q+1)=n+1+s

.

Los premios y los récords

La tabla siguiente hace un recorrido por todos los números RSA.

Los números del desafío en líneas rosas son números expresados en base 10, mientras que los de las líneas amarillas son números expresados en base 2, y que tenían un premio asignado.

Número RSA	Cifras decimales	Cifras binarias	Premio ofrecido	Factorizado en	Factorizado por
RSA-100	100	330		abril de 1991	Arjen K. Lenstra
RSA-110	110	364		abril de 1992	Arjen K. Lenstra y M.S. Manasse
RSA-120	120	397		junio de 1993	T. Denny et al.
RSA-129	129	426	$100 USD	abril de 1994	Arjen K. Lenstra et al.
RSA-130	130	430		10 de abril de 1996	Arjen K. Lenstra et al.
RSA-140	140	463		2 de febrero de 1999	Herman J. J. te Riele et al.
RSA-150^[1]	150	496		16 de abril de 2004	Kazumaro Aoki et al.
RSA-155	155	512		22 de agosto de 1999	Herman J. J. te Riele et al.
RSA-160	160	530		1 de abril de 2003	Jens Franke et al., Universidad de Bonn
RSA-170	170	563		abierto
RSA-576	174	576	$10,000 USD	3 de diciembre de 2003	Jens Franke et al., Universidad de Bonn
RSA-180	180	596		abierto
RSA-190	190	629		abierto
RSA-640	193	640	$20,000 USD	2 de noviembre de 2005	Jens Franke et al., Universidad de Bonn
RSA-200	200	663		9 de mayo de 2005	Jens Franke et al., Universidad de Bonn
RSA-210	210	696		26 de septiembre de 2013	Ryan Propper
RSA-704	212	704	$30,000 USD	abierto
RSA-220	220	729		abierto
RSA-230	230	762		abierto
RSA-232	232	768		abierto
RSA-768	232	768	$50,000 USD	12 de diciembre de 2009	A six-institution research team led by T. Kleinjung
RSA-240	240	795		2 de diciembre de 2019	Fabrice Boudot et al.
RSA-250	250	829		abierto
RSA-260	260	862		abierto
RSA-270	270	895		abierto
RSA-896	270	896	$75,000 USD	abierto
RSA-280	280	928		abierto
RSA-290	290	962		abierto
RSA-300	300	995		abierto
RSA-309	309	1024		abierto
RSA-1024	309	1024	$100,000 USD	abierto
RSA-310	310	1028		abierto
RSA-320	320	1061		abierto
RSA-330	330	1094		abierto
RSA-340	340	1128		abierto
RSA-350	350	1161		abierto
RSA-360	360	1194		abierto
RSA-370	370	1227		abierto
RSA-380	380	1261		abierto
RSA-390	390	1294		abierto
RSA-400	400	1327		abierto
RSA-410	410	1360		abierto
RSA-420	420	1393		abierto
RSA-430	430	1427		abierto
RSA-440	440	1460		abierto
RSA-450	450	1493		abierto
RSA-460	460	1526		abierto
RSA-1536	463	1536	$150,000 USD	abierto
RSA-470	470	1559		abierto
RSA-480	480	1593		abierto
RSA-490	490	1626		abierto
RSA-500	500	1659		abierto
RSA-617	617	2048		abierto
RSA-2048	617	2048	$200,000 USD	abierto

↑ La seguridad de RSA retiró el RSA-150 del desafío original, pero fue factorizado de todas formas.

Véase también

Problema RSA
The Magic Words are Squeamish Ossifrage, la solución encontrada en 1994 a RSA-129, el primer desafío, propuesto en 1977

Enlaces externos

Datos: Q1785397

[rsa150-1] La seguridad de RSA retiró el RSA-150 del desafío original, pero fue factorizado de todas formas.

[1]